package com.origin.niuke;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/17 19:45
 * 字符串出现次数的TopK问题
 * 算法：哈希 + 堆
 */
public class NC97 {

    public String[][] topKstrings (String[] strings, int k) {
        // write code here
        Map<String, Integer> map = new HashMap<>();
        for (String s : strings) map.put(s, map.getOrDefault(s, 0) + 1);
        PriorityQueue<String[]> queue = new PriorityQueue<>(k, (a, b) -> {
            if (!a[1].equals(b[1])) return Integer.parseInt(b[1]) - Integer.parseInt(a[1]);
            return a[0].compareTo(b[0]);
        });
        map.forEach((key, val) -> queue.offer(new String[]{key, val + ""}));
        String[][] ans = new String[k][2];
        for (int i = 0; i < k; i++) ans[i] = queue.poll();
        return ans;
    }

}
